class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int n = score.size();
        vector<string> ret(n);
        priority_queue<pair<int, int>> heap;
        for (int i = 0; i < n; i++) heap.push({ score[i], i });
        int j = 1;
        while (!heap.empty())
        {
            if (j == 1) {
                ret[heap.top().second] = "Gold Medal";
            }
            else if (j == 2) {
                ret[heap.top().second] = "Silver Medal";
            }
            else if (j == 3) {
                ret[heap.top().second] = "Bronze Medal";
            }
            else {
                ret[heap.top().second] = to_string(j);
            }
            j++;
            heap.pop();
        }
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pst;
        stack<TreeNode*> qst;
        getPath(root, pst, p);
        getPath(root, qst, q);

        while (pst.size() != qst.size())
        {
            if (pst.size() > qst.size()) {
                pst.pop();
            }
            else {
                qst.pop();
            }
        }
        while (pst.top() != qst.top())
        {
            pst.pop();
            qst.pop();
        }
        return pst.top();
    }
    bool getPath(TreeNode* root, stack<TreeNode*>& st, TreeNode* x)
    {
        if (!root) return false;

        st.push(root);
        if (root == x) return true;

        if (getPath(root->left, st, x)) return true;
        if (getPath(root->right, st, x)) return true;

        st.pop();
        return false;
    }
};